Como descrevemos matematicamente os fios invisíveis que conectam a sociedade? Seja o Números de Bacon ligando Bela Lugosi a ícones de Hollywood ou Grafos de Similaridade agrupando pontos de dados com base na proximidade, Teoria dos Grafos fornece a linguagem formal $G = (V, E)$ para modelar esses universos discretos.
1. A Anatomia dos Grafos
No seu cerne, um grafo consiste em um conjunto de vértices ($V$) e um conjunto de arestas ($E$). No entanto, as regras de funcionamento variam conforme a estrutura:
- Grafo Simples: A forma mais elegante; proíbe laços (arestas que conectam um vértice a si mesmo) e arestas paralelas (arestas redundantes entre os mesmos dois pontos).
- Multigrafo: Permite laços e arestas paralelas, frequentemente usado para modelar múltiplos tipos de interações (por exemplo, texto versus chamada) entre os mesmos dois nós.
- Vértice Isolado: Um vértice $v$ é isolado se nenhuma aresta incidir sobre ele, representando um objeto sem relações no conjunto atual.
Na ciência de dados, usamos frequentemente uma Função de Dissimilaridade para construir grafos:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Traçamos uma aresta entre $v$ e $w$ apenas se $s(v, w)$ estiver abaixo de um valor limite específico, efetivamente construindo uma rede de "vizinhos".
2. Caminhos, Conectividade e Componentes
Um caminho é uma sequência de vértices e arestas. Se um caminho visitar cada vértice apenas uma vez, ele é um caminho simples. A conectividade é o coração do grafo:
- Grafo Conectado: Existe um caminho entre todos cada par de vértices no grafo.
- Componentes: Se um grafo não for conectado, ele se divide em partes disjuntas chamadas componentes. Cada componente é um subgrafo conexo máximo.
3. Subgrafos: A Arquitetura dos Subconjuntos
Um subgrafo $G' = (V', E')$ é um subconjunto de um grafo $G$ tal que todo vértice em $V'$ existe em $V$, e toda aresta em $E'$ conecta vértices encontrados em $V'$. Identificar subgrafos é fundamental para detectar padrões locais dentro de redes globais.